package pro.softzhang.algo.lc;

import pro.softzhang.algo.flag.book.BCrackingVI;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

@BCrackingVI(0401)
public class RouteBetweenNodesLCCI {
    public static void main(String[] args) {

    }

    static class Solution {
        public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
            Set<Integer>[] a = new Set[n];
            for (int i = 0; i < n; i++)
                a[i] = new HashSet<>();

            for (int[] edge : graph)
                a[edge[0]].add(edge[1]);

            boolean[] visited = new boolean[n];
            visited[start] = true;
            Queue<Integer> q = new LinkedList<>();
            q.offer(start);
            while (!q.isEmpty() && !visited[target]) {
                int vertex = q.poll();
                Set<Integer> b = a[vertex];
                for (int next : b) {
                    if (!visited[next]) {
                        visited[next] = true;
                        q.offer(next);
                    }
                }
            }
            return visited[target];
        }
    }
}
